Since the divestiture of the American Telephone & Telegraph Company in 1984, the Regional Bell Holding Companies (RBHCs) have focused their efforts on cutting operating costs, upgrading their networks, providing new high speed services, and interconnecting their networks to long-distance companies and international carriers. One of the tools the RBHCs have chosen to achieve these goals is the Synchronous Optical Network (SONET). SONET is both a standard and a set of specifications for building high speed, digital communications networks that run over fiberoptic cables while interfacing with existing electrical protocols and asynchronous transmission equipment. Fiberoptics has revolutionized telecommunications in view of the large bandwidth availability (currently estimated in the hundreds of gigabits per second) which continues to increase with technological advances such as wave-division multiplexing and similar developments in light polarization and dispersion-shifted fibers.
As those skilled in the art will recognize, SONET specifies a digital hierarchy based on Optical Carrier (OC) rather than electrical levels. SONET does define Synchronous Transport Signals (STS), however, which are electrical interfaces used as the multiplexing mechanisms within SONET Network Elements (NE). Network elements combine STS-1s as needed up to STS-N where N is the number of STS-1s, then convert the total electrical multiplex to an optical carrier and transmit it over optical fiber. SONET is multiplexed at the byte level, allowing services to be dynamically placed into the broadband STS for transport. The basic SONET of 64 Kbps per byte is the same speed as the conceptual voice channel DSO allowing SONET to easily integrate all currently used digital services into the optical hierarchy.
One of the principal benefits of SONET is that it allows for the direct multiplexing of current network services, such as DS1, DS1C, DS2, and DS3 into the synchronous payload of STS-1. As those skilled in the art will recognize, the above rates, as in the case of most defined rates, were developed based on existing transmission systems. For example, the DS1 and DS2 signal rates (1.544 million bits per second and 6.312 million bits per second) are the transmission rates of the T1 and T2 wire pair carrier systems. Initially, one multiplexer, called an M12, was used to combined four DS1 channels into a DS2, and a second multiplexer, called an M23, was used to combine seven DS2 channels into a DS3. Presently, most networks use a single multiplexer termed an M13, which combines twenty-eight DS1 channels into a DS3. Of course, one of the key attributes of these previous multiplexer designs is that they permit DS1 signals to be timed independently, i.e. asynchronous multiplexing. Bits can therefore be sent at different transmission rates because individual channels need not be synchronized to a common timing source.
The asynchronous DS3 multiplexing standard was implemented in the days when most networks utilized analog technology and the few digital systems in existence generated their own clocking systems. Significantly, the transmission specifications for DS1 signals specify that the bit rate is 1.544 million bits per second, plus or minus 75 bps. To compensate for this range, additional bits must therefore be "stuffed" into each DS1 signal before they are multiplexed to a higher rate. Again, as those skilled in the art will recognize, while bit stuffing supports independently clocked input signals, it also makes it nearly impossible to locate individual DS1 or DSO channels within a DS3 bit stream. To extract a single channel, a DS3 signal would need to first be demultiplexed through M13 components into twenty-eight DS1s before the channels could be switched or rearranged. As a result, the process of adding or deleting channels is expensive.
In contrast to asynchronous multiplexing, the SONET standard defines a viable alternative which supports greater capacity and efficiency. In the SONET multiplexing format, the basic signal transmission rate--STS-1--operates at 51.84 million bits per second. AN STS-1 can carry 28 DS1 signals or one asynchronous DS3. STS-1 signals are then multiplexed to produce higher bit rates--STS-2, STS-3, etc. As referenced above, the other term used to define the SONET signal levels is optical carrier. The bit rates are the same in each case, so the bit rate of the STS-1 equals the bit rate of the OC-1. The only difference is the type of signal that is being referenced. For example, if the signal is in an electrical format, it is referred to as an STS. Similarly, if the signal is in an optical format--compatible with a fiber medium--it is referred to as an OC.
The SONET standards define an alternative to asynchronous DS3 multiplexing, which describes how to divided STS signals into lower speed increments, i.e. virtual tributaries. The major advantage of synchronous multiplexing is that when DS1 and other low-speed channels are multiplexed directly into the STS format, the lower speed channels can be identified and reconfigured for drop-and-insert. As a result, the drop-and-insert process can be done simpler with less expense of hardware then the back-to-back M13 multiplexers used in asynchronous multiplexing.
Because of the large bandwidth availability in fiber, and the growing volume of data traffic, disruptions from link and node failures due to cable cuts, for example, become increasingly serious. Network survivability has therefore become a major concern for SONET designers and has fueled interest in what is known in the art as "ring" architectures. Such architectures take advantage of the capability provided by synchronous multiplexing in SONET to eliminate the need to backhaul traffic to central hubs. Thus, at each switching office, the SONET transport node directly accesses the required time slots in the bit stream through the use of modified Add-Drop Multiplexers (ADM). The SONET ring topology permits the creation of highly survivable networks which are viewed in the communications industry as essential for obtaining business for critical data communications.
In most cases, the deployment of SONET rings results in cost savings since it is far less expensive for carriers to install a fiber ring then to deploy point-to-point links. Consider, for example, a rural route, where linking remote terminals to a central office in a point-to-point application would require six multiplexers--one at each site and at the Central Office (CO) for each route--and six fibers, two to each site. In a ring topology, all that is required is one multiplexer at the CO and two fibers that go through a multiplexer at each site for a total of four multiplexers and two fibers. Significantly, in the ring topology, working or service traffic is routed in one direction only. If that fiber fails, traffic is rerouted on a protection fiber to flow in the opposite direction. In this manner, working traffic bypasses the failure to get to its proper destination.
Against this background, it is readily seen that there is significant debate in the communications industry regarding the type and location of rings, and in particular, Self-Healing Rings (SHR) to deploy. As those skilled in the art will recognize, the directionality of service routing and the protection mechanism are key attributes that distinguish different self-healing ring architectures. For example, a unidirectional ring routes service traffic in only one direction of the ring. On the other hand, a bidirectional ring routes the components of a duplex circuit in opposite directions on the ring. Similarly, in a path-switched ring, traffic is protected on a per path basis, and the switching is based on the health of each individual path where it exits the ring. Still further, in a line-switched ring, switching is based on the health of the line between each pair of nodes. Thus, when a line is faulty, the entire line is switched off to a protection loop at the failure's boundaries.
Based on the foregoing, two architectures have gained prominence for deployment in SONET networks. These are the two-fiber unidirectional path-switched rings (alternately termed path-switched rings), and two and four fiber bidirectional line-switched rings (alternately termed bidirectional rings).
Because of the importance of the proper design and implementation of self-healing rings, network designers are generally required to spend hundreds of hours in designing such networks in order to achieve the most cost-effective solution based upon projected demand. General methods and systems for allocating resources in telecommunication facilities are known generally in the art. As disclosed, for example, by U.S. Pat. No. 4,744,028 to Karmarkar. This patent discloses a method and system for allocating available telecommunication transmission facilities among subscribers demanding service at a particular time. An objective of the method and system is to reduce the total operation cost of the transmission facilities.
In the method and system disclosed by Karmarkar, subscribers and total cost are linearly related. The method and system tentatively and iteratively assign telecommunication transmission facilities to customers, determining each reassignment by normalizing a previous assignment in view of allocation constraints. These reiterative steps are terminated when the cost is found to be less than a threshold value, and an allocation and transmission facilities is made accordingly.
A similar method is disclosed in U.S. Pat. No. 4,744,026 to Vanderbei. This patent discloses a method for allocating available industrial facilities among users thereof and has an objective of reducing the total costs for providing the facilities. In the disclosed method, available facilities are tentatively and iteratively assigned to users according to an algorithm to reduce costs.
As in the case of Karmarkar, the method disclosed in Vanderbei requires that each reassignment be determined by normalizing a previous assignment in view of allocation constraints. During each reassignment, changes with respect to a previous assignment are adjusted, in terms of their direction, under the assumption that at least one constraint increases in value without limit. The reiterative steps are terminated when the cost if found to be less than a threshold value, and an allocation of transmission facilities is made according to the final, reduced-cost assignment.
While each of the above disclosed methods for allocating communication resources functions with a certain degree of efficiency, none disclose the advantages of the improved method and system for designing and implementing self-healing rings of the present invention as is hereinafter more fully described.